package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0056 extends Printer {

    public static void main(String[] args) {
        Solution_0056 solution = new Solution_0056();
//        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] intervals = {{1, 4}, {4, 5}};
//        int[][] intervals = {{2, 3}, {4, 5}, {6, 7}, {1, 10}};
        int[][] s = solution.merge(intervals);
        print(s);
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] line = intervals[i];
            for (int j = 0; j < list.size(); j++) {
                int[] exist = list.get(j);
                if (exist[0] == line[0] && exist[1] == line[1]) {
                    list.remove(j);
                    j--;
                } else if (exist[0] <= line[1] && exist[1] >= line[0]) {
                    line[0] = Math.min(exist[0], line[0]);
                    line[1] = Math.max(exist[1], line[1]);
                    list.remove(j);
                    j--;
                }
            }
            list.add(line);
        }
        return list.toArray(new int[list.size()][2]);
    }
}
